This invention relates to performing Cholesky decomposition operations in integrated circuit devices, and particularly in programmable integrated circuit devices such as programmable logic devices (PLDs).
Certain matrix operations require that a matrix be factored. For example, factoring a matrix may be necessary when a matrix is to be inverted. The result may be a “triangulated” matrix—i.e., a matrix with no values above the diagonal. The consequence is that only the values on the diagonal, and in the columns below those values, need to be calculated.
In Cholesky decomposition, to factor a matrix a, the first element ljj, at the top of each column in the resultant triangulated matrix l, may be calculated as:ljj=√{square root over (ajj−Lj,Lj)}where ajj is the jjth element of the original matrix a, and Lj is vector representing the jth row of matrix l up to the (j−1)th column. The subsequent elements in the jth column may be calculated as:
      l    ij    =                    a        ij            -              〈                              L            i                    ,                      L            j                          〉                    l      jj      where aij is the ijth element of the original matrix a, and Li is vector representing the portion of the ith row of matrix l up to the (j−1)th column. To perform this calculation, the ljj term needs to be calculated before any of the lij elements can be calculated. The inner product in each term—which, in the case of all real values is the same as a dot product, but in the case of complex values requires taking the complex conjugate of the second vector—may require dozens of clock cycles. Moreover, the square root calculation in the computation of ljj can also take dozens of clock cycles.